// https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/

// 算法思路总结：
// 1. 贪心策略处理用最少数量的箭引爆气球
// 2. 按区间右端点排序（或按左端点排序后维护最小右边界）
// 3. 维护当前箭矢的射击范围（交集区间）
// 4. 当新区间与当前范围无重叠时，需要新增箭矢
// 5. 时间复杂度：O(nlogn)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int findMinArrowShots(vector<vector<int>>& points) 
    {
        int m = points.size();
        if (m == 1) return 1;

        sort(points.begin(), points.end(), [](const vector<int>& v1, const vector<int>& v2){
            return v1[0] < v2[0];
        });

        int ret = 0;
        int l = points[0][0], r = points[0][1];
        for (int i = 1 ; i < m ; i++)
        {
            if (r < points[i][0])
            {
                ret++;
                r = points[i][1];
            }
            else if (r > points[i][1])
                r = points[i][1];
        }
        ret++;

        return ret;
    }
};

int main()
{
    vector<vector<int>> vv1 = {{10,16}, {2,8}, {1,6}, {7,12}};
    vector<vector<int>> vv2 = {{1,2}, {3,4}, {5,6}, {7,8}};

    Solution sol;

    cout << sol.findMinArrowShots(vv1) << endl;
    cout << sol.findMinArrowShots(vv2) << endl;

    return 0;
}